package com.heima.leetcode.practice;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 57. 插入区间
 * @date 2025/5/11 10:56
 */
public class E57 {

    public int[][] insert(int[][] intervals, int[] newInterval) {
        int i = 0, n = intervals.length;
        List<int[]> result = new ArrayList<>();
        // 一阶段
        while(i < n && intervals[i][1] < newInterval[0]){
            result.add(intervals[i]);
            i++;
        }
        // 二阶段
        while(i < n && intervals[i][0] <= newInterval[1]){
            newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
            newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
            i++;
        }
        result.add(newInterval);
        // 三阶段
        while(i < n){
            result.add(intervals[i]);
            i++;
        }
        return result.toArray(new int[result.size()][]);
    }

    public int[][] insert2(int[][] intervals, int[] newInterval) {
        if (intervals.length == 0) {
            return new int[][] { newInterval };
        }
        // Step 1: 初始化 left 和 right
        int left = newInterval[0];
        int right = newInterval[1];
        // Step 2: 确定合并后的 left 和 right
        for (int[] interval : intervals) {
            if (interval[1] >= left && interval[0] <= right) {
                left = Math.min(left, interval[0]);
                right = Math.max(right, interval[1]);
            }
        }
        // Step 3: 构建结果数组
        List<int[]> result = new ArrayList<>();
        boolean inserted = false; // 标记新区间是否已插入
        for (int[] interval : intervals) {
            if (interval[1] < left) {
                // 当前区间在 left 左侧，直接加入
                result.add(interval);
            } else if (interval[0] > right) {
                // 当前区间在 right 右侧，先插入新区间（如果未插入）
                if (!inserted) {
                    result.add(new int[] { left, right });
                    inserted = true;
                }
                result.add(interval);
            }
            // 当前区间被合并，跳过
        }
        // 如果新区间未被插入（例如在所有区间之后）
        if (!inserted) {
            result.add(new int[] { left, right });
        }
        return result.toArray(new int[result.size()][]);
    }
}
